//
// Created by chao.li on 2023/12/26.
//

#ifndef SOLUTIONS_SOLUTION025_H
#define SOLUTIONS_SOLUTION025_H

#include "../common.hpp"

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {

    // tail 是最后一个要翻转的节点
    tuple<ListNode*, ListNode*> reverseSubList(ListNode* head, ListNode* tail)
    {
        auto *ntail= head, *nhead = head;
        auto *p = head->next;

        while(p != nullptr){
            ntail->next = p->next;
            p->next = nhead;
            nhead = p;

            if(p == tail){
                break;
            } else{
                p = ntail->next;
            }
        }
        return {tail, head};
    }

    // 返回结果指向最后一个节点
    ListNode* getNext(ListNode* head, int k)
    {
        int i = 0;
        auto *p = head;
        while(i < k-1 && p != nullptr){
            p = p->next;
            i++;
        }
        return p;
    }

public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k <= 1){
            return head;
        }

        ListNode *newHead = nullptr, *lastSubTail = nullptr;
        auto *shead = head, *stail = head;

        stail = getNext(shead, k);
        while(stail != nullptr){
            std::tie(shead, stail) =  reverseSubList(shead, stail);
            if(lastSubTail != nullptr){
                lastSubTail->next = shead;
            }
            lastSubTail = stail;

            if(newHead == nullptr){
                newHead = shead;
            }
            shead = stail->next;

            stail = getNext(shead, k);
        }
        if(newHead == nullptr){
            newHead = head;
        }
        return newHead;
    }
};
//leetcode submit region end(Prohibit modification and deletion)

void test(){
    auto list = buildList({});
    Solution s;
    auto res = s.reverseKGroup(list, 6);
    printl(res);
}
#endif //SOLUTIONS_SOLUTION025_H
